//给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。 
//
// 示例: 
//
// 输入: 3
//输出:
//[
// [ 1, 2, 3 ],
// [ 8, 9, 4 ],
// [ 7, 6, 5 ]
//] 
// Related Topics 数组 
// 👍 228 👎 0

package leetcode.editor.cn;

//Java：螺旋矩阵 II
public class P59SpiralMatrixIi {

    /**
     *
     * 思路：这道题和54题很像，跟54题一样遍历就行了
     *
     * 执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗： 37.6 MB , 在所有 Java 提交中击败了 51.05% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] generateMatrix(int n) {
            int[][] matrix = new int[n][n];
            if (n > 0) {
                int yEnd = n - 1;
                int xEnd = n - 1;

                int xStart = 0;
                int yStart = 0;
                int num = 1;
                int total = n * n;
                while (num <= total) {
                    // →
                    for (int j = xStart; j < xEnd + 1 && num <= total; j++) {
                        matrix[yStart][j] = num++;
                    }

                    // ↓
                    for (int j = yStart + 1; j < yEnd && num <= total; j++) {
                        matrix[j][xEnd] = num++;
                    }

                    // ←
                    for (int j = xEnd; j >= xStart && num <= total; j--) {
                        matrix[yEnd][j] = num++;
                    }

                    // ↑
                    for (int j = yEnd - 1; j > yStart && num <= total; j--) {
                        matrix[j][xStart] = num++;
                    }
                    xStart++;
                    xEnd--;
                    yStart++;
                    yEnd--;
                }
            }
            return matrix;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P59SpiralMatrixIi().new Solution();
        int[][] a = solution.generateMatrix(0);
        System.out.println(a);
        // TO TEST
    }

}